package com.dzsw.datastruct.tree.binary;

import java.util.*;

public class IterationBinaryTreeImpl<E> extends AbstractBinaryTreeImpl<E> {

    @Override
    public void preOrder(Visitor<E> visitor) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        preOrder(this.root, visitor);
    }

    /**
     * 前序遍历（迭代），根、左、右
     * 1. tempNode != null 时，就保存这个节点值到 list 中，然后将其入栈并置 tempNode 为它自己的左子节点。
     * 2. tempNode == null 时，说明已经遍历到二叉树的左下节点了，这时前序遍历应该遍历右子树了，首先 pop 出已经遍历保存过的父节点，然后置 tempNode 为 pop 出的父节点的右子节点。
     *
     * @param node
     * @param visitor
     */
    private void preOrder(Node<E> node, Visitor<E> visitor) {
        Stack<Node<E>> stack = new Stack<>();
        Node<E> tempNode = node;
        while (!stack.isEmpty() || tempNode != null) {
            if (tempNode != null) {
                if (visitor.isStop()) {
                    return;
                }
                visitor.setStop(visitor.visit(tempNode.getElement()));
                stack.push(tempNode);
                tempNode = tempNode.getLeft();
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.getRight();
            }
        }
    }

    @Override
    public void inOrder(Visitor<E> visitor) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        List<E> list = new ArrayList<>();
        inOrder(this.root, visitor);
    }

    /**
     * 中序遍历（迭代），左、根、右
     * 1. tempNode != null 时，说明还有左子节点存在，将 tempNode 入栈，并且将 tempNode 置为它自己的左子节点。（和前序遍历的区别在于这里遍历到先不保存到 list 中，出栈的时候再将其保存到 list 中）
     * 2. tempNode == null 时，说明到二叉树左下的节点了，这时栈顶的父节点出栈赋值给 tempNode ，并保存节点值到 list ，将 tempNode 置为栈顶节点的右子节点继续循环。
     *
     * @param node
     * @param visitor
     */
    private void inOrder(Node<E> node, Visitor<E> visitor) {
        Stack<Node<E>> stack = new Stack<>();
        Node<E> tempNode = node;
        while (!stack.isEmpty() || tempNode != null) {
            if (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.getLeft();
            } else {
                tempNode = stack.pop();
                if (visitor.isStop()) {
                    return;
                }
                visitor.setStop(visitor.visit(tempNode.getElement()));
                tempNode = tempNode.getRight();
            }
        }
    }

    @Override
    public void postOrder(Visitor<E> visitor) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        postOrder(this.root, visitor);
    }

    /**
     * 后序遍历（迭代），左、右、根
     * 1. 对应前序遍历的反向操作。
     * 2. 前序遍历从尾部添加元素，后序遍历从头部添加元素。
     * 3. 前序遍历先去左子树，后续遍历先去右子树。
     *
     * @param node
     * @param visitor
     */
    private void postOrder(Node<E> node, Visitor<E> visitor) {
        Stack<Node<E>> stack = new Stack<>();
        Node<E> tempNode = node;
        while (!stack.isEmpty() || tempNode != null) {
            if (tempNode != null) {
                stack.push(tempNode);
                if (visitor.isStop()) {
                    return;
                }
                visitor.setStop(visitor.visit(tempNode.getElement()));
                tempNode = tempNode.getRight();
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.getLeft();
            }
        }
    }

    @Override
    public int height() {
        if (root == null) {
            return 0;
        }
        return height(this.root);
    }

    /**
     * (迭代法)获取树的高度，层序遍历
     * @return
     */
    private int height(Node<E> root) {
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }

            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }

            // 意味着即将要访问下一层
            if (levelSize == 0) {
                //每一层访问完后，下一层的节点个数是队列的size
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }
}
